#include "OptimizerMcmfPlanA.hpp"

extern long beginTime;
extern int drop_out, cycleCnt;
OptimizerMcmfPlanA::OptimizerMcmfPlanA(DataManager* _dataManager)
{
	INFINITY_CAPICITY = 0x3f3f3f3f3f3f3f;
	this->dataManager = _dataManager;
	this->timeNum = this->dataManager->getTotalTime();
	this->dataManager->getQosGraph(siteNum, clientNum, graphSiteToClient);

	bandwidthDemand.resize(timeNum + 1, std::vector<int>{});
	for (int time = 1; time <= timeNum; ++time)
	{
		this->dataManager->getDemands(time, bandwidthDemand[time]);
	}
	this->dataManager->getSiteLimits(bandwidthLimit);

	rank95 = timeNum * 9.5;
	if (rank95 % 10 != 0) rank95 = rank95 / 10 + 1;
	else rank95 = rank95 / 10;

	siteValue.resize(siteNum + 1, std::vector<int>(timeNum + 1, 0));
	localSiteValue.resize(siteNum + 1, 0);
	bestSiteValue.resize(siteNum + 1, std::vector<int>(timeNum + 1, 0));
	siteValueSortRank.resize(siteNum + 1, std::vector<int>(timeNum + 1, 0));
	localSiteValueSortRank.resize(siteNum + 1,0);
	bestSiteValueSortRank.resize(siteNum + 1, std::vector<int>(timeNum + 1, 0));	
	siteValueTimeRank.resize(siteNum + 1, std::vector<int>(timeNum + 1, 0));
	localSiteValueSiteRank.resize(siteNum + 1, 0);
	bestSiteValueTimeRank.resize(siteNum + 1, std::vector<int>(timeNum + 1, 0));
	edge.resize(graphSiteToClient.size() + 1, Edge{ 0, 0, 0 });
	head.resize(siteNum + 1, 0);
	cnt = 0;

	for (auto pair : graphSiteToClient)
	{
		insert(pair.first, pair.second);
	}

	mcmf = new MCMF(siteNum, clientNum);
	maxFlow = new Flow(siteNum, clientNum);

	log.resize(timeNum + 1, std::vector<std::vector<std::pair<int, int>>>(clientNum + 1, std::vector<std::pair<int, int>>{}));
	bestLog.resize(timeNum + 1, std::vector<std::vector<std::pair<int, int>>>(clientNum + 1, std::vector<std::pair<int, int>>{}));

	timeTotalDemand.resize(timeNum + 1, 0);
	for (int time = 1; time <= timeNum; ++time)
	{
		timeTotalDemand[time] = 0;
		for (int clientID = 1; clientID <= clientNum; ++clientID)
		{
			timeTotalDemand[time] += bandwidthDemand[time][clientID];
		}
	}
	maxSiteBandwidth.resize(timeNum + 1, 0);

	lastBinaryAns.resize(timeNum + 1, 0);

	bestAns = 0;

}

void OptimizerMcmfPlanA::insert(int u, int v)
{
	edge[++ cnt] = Edge{ u, v, head[u] };
	head[u] = cnt;
}


void OptimizerMcmfPlanA::sortSiteValue(int siteID)
{
	for (int time = 1; time <= timeNum; ++time)
		siteValueSortRank[siteID][time] = time;
	std::sort(siteValueSortRank[siteID].begin() + 1, siteValueSortRank[siteID].end(), [=](int a, int b) {
		return siteValue[siteID][a] < siteValue[siteID][b];
		});

	//if (siteID == 85)
	//	std::cout << siteID << ":";
	for (int rank = 1; rank <= timeNum; ++rank)
	{
		siteValueTimeRank[siteID][siteValueSortRank[siteID][rank]] = rank;
		//if (siteID == 85)
		//	std::cout << "[" << rank << ", " << siteValueSortRank[siteID][rank] << "], " << siteValue[siteID][siteValueSortRank[siteID][rank]] << "\n";
	}
}

bool OptimizerMcmfPlanA::updateBestAns()
{
	int sum = 0;
	for (int siteID = 1; siteID <= siteNum; ++siteID)
	{
		sum += siteValue[siteID][siteValueSortRank[siteID][rank95]];
	}

	if (sum < bestAns || bestAns == 0)
	{
		bestAns = sum;
		bestLog = log;
		bestSiteValue = siteValue;
		bestSiteValueSortRank = siteValueSortRank;
		bestSiteValueTimeRank = siteValueTimeRank;
		return true;
	}
	return false;
}

void OptimizerMcmfPlanA::updateLocalSiteValue(int time)
{
	for (auto& num : localSiteValue)
	{
		num = 0;
	}
	for (int clientID = 1; clientID <= clientNum; ++clientID)
	{
		for (auto& pair : log[time][clientID])
		{
			localSiteValue[pair.first] += pair.second;
		}
	}
	sortLocalSiteValue(time);
}

void OptimizerMcmfPlanA::sortLocalSiteValue(int time)
{
	for (int siteID = 1; siteID <= siteNum; ++siteID)
		localSiteValueSortRank[siteID] = siteID;
	std::sort(localSiteValueSortRank.begin() + 1, localSiteValueSortRank.end(), [=](int a, int b) {
		return localSiteValue[a] < localSiteValue[b];
		});

	//if (siteID == 85)
	//	std::cout << siteID << ":";
	for (int rank = 1; rank <= siteNum; ++rank)
	{
		localSiteValueSiteRank[localSiteValueSortRank[rank]] = rank;
		//if (siteID == 85)
		//	std::cout << "[" << rank << ", " << siteValueSortRank[siteID][rank] << "], " << siteValue[siteID][siteValueSortRank[siteID][rank]] << "\n";
	}
}

void OptimizerMcmfPlanA::setFlowGraphWithLocal(int limitFlow, int time, int currentCycle)
{
}

extern int maxFlowBinaryCnt;
extern double maxFlowK;
void OptimizerMcmfPlanA::initSiteValueFromMaxFlow()
{
	for (int time = 1; time <= timeNum; ++time)
	{
		// if(time%100==0)std::cout << "time " << time << "\n"; 			
		int left, right, mid, ans;
		int cnt;
		left = 0, right = maxSiteBandwidth[time], ans = right;
		cnt = 0;
		while (left < right && (cnt < maxFlowBinaryCnt || ans == maxSiteBandwidth[time]))
		{
			cnt++;
			maxFlow->clear();
			mid = (right - left) * maxFlowK + left;
			setMaxFlow(mid, time);
			if (runMaxFlow(time, false)) right = mid - 1, ans = mid;
			else left = mid + 1;
		}
		maxFlow->clear();
		setMaxFlow(ans, time);
		if (!runMaxFlow(time, true)) std::cout << "error!\n";
	}
	updateSiteValueFromMaxFlow();
	log.clear();
	log.resize(timeNum + 1, std::vector<std::vector<std::pair<int, int>>>(clientNum + 1, std::vector<std::pair<int, int>>{}));
}

void OptimizerMcmfPlanA::setMaxFlow(int limitFlow, int time)
{
	//Source to Site,	capicity: bandwidthLimit
	for (int siteID = 1; siteID <= siteNum; ++siteID)
	{
		maxFlow->addEdgeFromSource(siteID, std::min(bandwidthLimit[siteID], limitFlow));
	}

	//Site to Client,	capicity: infinity
	for (int siteID = 1; siteID <= siteNum; ++siteID)
	{
		for (int pos = head[siteID]; pos; pos = edge[pos].nxt)
		{
			int clientID = edge[pos].v;
			maxFlow->addEdge(siteID, clientID, INFINITY_CAPICITY);
		}
	}

	//Client to Target,	capicity: bandwidthDemand,	cost: 0
	for (int clientID = 1; clientID <= clientNum; ++clientID)
	{
		maxFlow->addEdgeToTarget(clientID, bandwidthDemand[time][clientID]);
	}
}

bool OptimizerMcmfPlanA::runMaxFlow(int time, bool addLog = false)
{
	int flow = maxFlow->getMaxFlow();
	if (addLog)
	{
		for (int clientID = 1; clientID <= clientNum; ++clientID)
		{
			maxFlow->getSponsors(clientID, log[time][clientID]);
		}
	}
	if (flow != timeTotalDemand[time]) return false;
	return true;
}

void OptimizerMcmfPlanA::updateSiteValueFromMaxFlow()
{
	for (auto& vec : siteValue)
	{
		for (auto& num : vec)
		{
			num = 0;
		}
	}
	for (int time = 1; time <= timeNum; ++time)
	{
		for (int clientID = 1; clientID <= clientNum; ++clientID)
		{
			for (auto& pair : log[time][clientID])
			{
				siteValue[pair.first][time] += pair.second;
			}
		}
	}
	for (int siteID = 1; siteID <= siteNum; ++siteID)
		sortSiteValue(siteID);

	updateBestAns();
}


void OptimizerMcmfPlanA::initSiteValue()
{
	for (int siteID = 1; siteID <= siteNum; ++siteID)
	{
		for (int time = 1; time <= timeNum; ++time)
		{
			int sum = 0;
			for (int pos = head[siteID]; pos; pos = edge[pos].nxt)
			{
				int clientID = edge[pos].v;
				sum += bandwidthDemand[time][clientID];
			}
			siteValue[siteID][time] = std::min(sum, bandwidthLimit[siteID]);
			maxSiteBandwidth[time] = std::max(maxSiteBandwidth[time], siteValue[siteID][time]);
		}
		sortSiteValue(siteID);
	}
}

void OptimizerMcmfPlanA::setFlowGraph(int limitFlow, int time, int currentCycle)
{
	//std::cout << cycleCnt << ", " << currentCycle << "\n";
	//Source to Site,	capicity: bandwidthLimit,	cost: siteValue
	for (int siteID = 1; siteID <= siteNum; ++siteID)
	{
				int ___ = .1*timeNum;
		int _2__ = 0;
		if (siteValueTimeRank[siteID][time] > rank95)
		{
			int abab = 0;
			bool flag = false;
			if(currentCycle >= cycleCnt * 7.0/9.0){
				abab = max(-1 * (9.0 * drop_out) / cycleCnt * currentCycle + 9 * drop_out, 10.0);
				
			}else{
				//flag = (rand()%100+1<=max(-1 * (3.0 * drop_out) / cycleCnt * currentCycle + 3 * drop_out, 10.0));
				abab = max((9.0 * drop_out) * currentCycle / (7 * cycleCnt), 10.0);
			}
			// std::cout << cycleCnt << ", " << currentCycle <<", "<<abab << "\n";
			flag = rand() % 100 + 1 <= abab;
			if(flag && _2__ < ___){
				mcmf->addEdgeFromSource(siteID, bandwidthLimit[siteID], 2);
			}else{
				mcmf->addEdgeFromSource(siteID, bandwidthLimit[siteID], 0);
			}
		}
		else
		{
			/*if(rand()%2 == 1 &&!___){
				___++;
			mcmf->addEdgeFromSource(siteID, std::min(bandwidthLimit[siteID], limitFlow), 0);
			}else*/
			mcmf->addEdgeFromSource(siteID, std::min(bandwidthLimit[siteID], limitFlow), 2);
		}
	}

	//Site to Client,	capicity: infinity,			cost: 0
	for (int siteID = 1; siteID <= siteNum; ++siteID)
	{
		for (int pos = head[siteID]; pos; pos = edge[pos].nxt)
		{
			int clientID = edge[pos].v;
			mcmf->addEdge(siteID, clientID, INFINITY_CAPICITY, 0);
		}
	}

	//Client to Target,	capicity: bandwidthDemand,	cost: 0
	for (int clientID = 1; clientID <= clientNum; ++clientID)
	{
		mcmf->addEdgeToTarget(clientID, bandwidthDemand[time][clientID], 0);
	}
}

void OptimizerMcmfPlanA::updateSiteValue()
{
	for (auto& vec : siteValue)
	{
		for (auto& num : vec)
		{
			num = 0;
		}
	}
	for (int time = 1; time <= timeNum; ++time)
	{
		for (int clientID = 1; clientID <= clientNum; ++clientID)
		{
			for (auto& pair : log[time][clientID])
			{
				siteValue[pair.first][time] += pair.second;
			}
		}
	}
	for (int siteID = 1; siteID <= siteNum; ++siteID)
		sortSiteValue(siteID);
	updateBestAns();
}

extern int binaryTotCnt, binaryCorrectCnt;
bool OptimizerMcmfPlanA::runFlow(int time, bool addLog)
{
	int flow;
	long long cost;
	mcmf->mcmf(flow, cost);
	if (addLog)
	{
		for (int clientID = 1; clientID <= clientNum; ++clientID)
		{
			mcmf->getSponsor(clientID, log[time][clientID]);
		}
	}
	if (flow != timeTotalDemand[time]) return false;
	return true;
}


void OptimizerMcmfPlanA::generateOutAnswer()
{
	for (int time = 1; time <= timeNum; ++time)
	{
		dataManager->setTime(time);
		for (int clientID = 1; clientID <= clientNum; ++clientID)
		{
			dataManager->setClient(clientID);
			for (auto& pair : bestLog[time][clientID])
			{
				dataManager->writeLog(pair.first, pair.second);
			}
		}
	}
}
extern int binarySmallCnt;
extern double bigK;


extern int firstBinaryTotCnt, biggerBinaryTotCnt, smallerBinaryTotCnt;
extern int biggerTime, smallerTime;
extern int smallerBetterCnt;

extern double initial_speed, accelarate;

int OptimizerMcmfPlanA::solve(int cycleCnt, int binaryCnt, double k)
{
	initSiteValue();
	initSiteValueFromMaxFlow();
	for (; cycleCnt; --cycleCnt)
	{
		std::cout << "cycleCnt: " << cycleCnt << "\n";
		for (int time = 1; time <= timeNum; ++time)
		{
			//  if(time%100==0)std::cout << "time " << time << "\n"; 			
			int left, right, mid, ans ;
			int cnt;

			if (lastBinaryAns[time] == 0)
			{
				left = 0, right = maxSiteBandwidth[time], ans = right;
				cnt = 0;
				while (left < right && (cnt < binaryCnt || ans == maxSiteBandwidth[time]))
				{
					++binaryTotCnt;
					++firstBinaryTotCnt;
					cnt++;
					mcmf->clear();
					mid = (right - left) * k + left;
					setFlowGraph(mid, time, cycleCnt);
					if (runFlow(time, false)) right = mid - 1, ans = mid, ++binaryCorrectCnt;
					else left = mid + 1;
				}
				mcmf->clear();
				setFlowGraph(ans, time, cycleCnt);
				if (!runFlow(time, true)) std::cout << "error!\n";
				lastBinaryAns[time] = ans;
				binaryTotCnt = 0;
				binaryCorrectCnt = 0;
			}
			else
			{		
				mcmf->clear();
				setFlowGraph(lastBinaryAns[time], time, cycleCnt);
				double speed = initial_speed, current_k = 0.5, max_k = 0.95;
				// speed > 1, accelarate < 1
				if (!runFlow(time, false))
				{
					int tmpTime = ::time(0);
					left = lastBinaryAns[time], right = maxSiteBandwidth[time], ans = right;
					cnt = 0;
					while (left < right && (cnt < binarySmallCnt || ans == maxSiteBandwidth[time]))
					{
						++binaryTotCnt;
						++biggerBinaryTotCnt;
						cnt++;
						mcmf->clear();

						mid = (right - left) * (1.0 - current_k) + left;

						// if(cnt >= binarySmallCnt)
						// 	mid = (right - left) * (1.0 - k) + left;
						// else
						// 	mid = (right - left) * (1.0 - bigK) + left;

						setFlowGraph(mid, time, cycleCnt);
						if (runFlow(time, false)) {
							right = mid - 1, ans = mid, ++binaryCorrectCnt;
							current_k = min(max_k, current_k * speed); // if success, speed up
							speed = min(2.0, speed * (1 + accelarate));
						} else {
							left = mid + 1;
							current_k = 0.5; // if failed, reset k and speed
							speed = initial_speed;
						}
					}
					mcmf->clear();
					setFlowGraph(ans, time, cycleCnt);
					if (!runFlow(time, true)) std::cout << "error!\n";
					lastBinaryAns[time] = ans;
					biggerTime += ::time(0) - tmpTime;
				}
				else
				{
					int tmpTime = ::time(0);
					left = 0, right = lastBinaryAns[time], ans = right;
					cnt = 0;
					while (left < right && cnt < binarySmallCnt)
					{
						++binaryTotCnt;
						++smallerBinaryTotCnt;
						cnt++;
						mcmf->clear();
						mid = (right - left) * bigK + left;
						setFlowGraph(mid, time, cycleCnt);
						if (runFlow(time, false)) right = mid - 1, ans = mid, ++binaryCorrectCnt, ++smallerBetterCnt;
						else left = mid + 1;
					}
					mcmf->clear();
					setFlowGraph(ans, time, cycleCnt);
					if (!runFlow(time, true)) std::cout << "error!\n";
					lastBinaryAns[time] = ans;
					smallerTime += ::time(0) - tmpTime;
				}
			}
			//std::cout << ::time(0) - beginTime << "\n";
		}
		if (cycleCnt != 1)
		{
			updateSiteValue();
			log.clear();
			log.resize(timeNum + 1, std::vector<std::vector<std::pair<int, int>>>(clientNum + 1, std::vector<std::pair<int, int>>{}));
		}
		//std::cout << time(0) - beginTime << "\n";
	}

	updateSiteValue();
	generateOutAnswer();

	int sum = 0;
	for (int siteID = 1; siteID <= siteNum; ++siteID)
	{
		sum += siteValue[siteID][siteValueSortRank[siteID][rank95]];
	}
	std::cout << "origin ans: " << sum << "\n";

	return bestAns;
}




